Search for: All records

Let Kt ( x ) denote the Levin-Kolmogorov Complexity of the string x , and let MKtP denote the language of pairs ( x , k ) having the property that Kt ( x ) ≤ k. We demonstrate that: • MKtP ∉ Heur neg BPP (i.e., MKtP is two-sided error mildly average-case hard) iff infinitely-often OWFs exist. • MKtP ∉ Avg neg BPP (i.e., MKtP is errorless mildly average-case hard) iff EXP ≠ BPP. Taken together, these results show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between two-sided error and errorless average-case hardness of the MKtP problem. 

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors: — The prover’s (parallel) running time is \( T + \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . (In other words, the prover’s running time is essentially T for large computation times!) — The prover uses at most \( p \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) processors. — The communication and verifier complexity are both \( \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is \( T \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) when using p processors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct non-interactive argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to \( \mathrm{poly}\hspace{-2.0pt}\log (T\cdot p) \) factors. We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF. 

Although the definition of sequential equilibrium can be applied without change to games of imperfect recall, doing so leads to arguably inappropriate results. We redefine sequential equilibrium so that the definition agrees with the standard definition in games of perfect recall while still giving reasonable results in games of imperfect recall. The definition can be viewed as trying to capture a notion of ex ante sequential equilibrium. The picture here is that players choose their strategies before the game starts and are committed to it, but they choose it in such a way that it remains optimal even off the equilibrium path. A notion of interim sequential equilibrium is also considered. 

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: (a) the Learning with Errors (LWE) assumption (with subexponential modulusto- noise ratio); (b) a circular security conjecture regarding the Gentry- Sahai-Waters’ (GSW) encryption scheme and a Packed version of Regev’s encryption scheme. The circular security conjecture states that a notion of leakage-resilient security, that we prove is satisfied by GSW assuming LWE, is retained in the presence of an encrypted key-cycle involving GSW and Packed Regev.